# 找到从根节点到节点的路径，求相同的子串

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def find(node, path, val):
            if node is None:
                return []
            path.append(node)
            if node.val == val:
                return path
            left = find(node.left, path, val)
            if left != []:
                return left
            right = find(node.right, path, val)
            if right != []:
                return right
            path.pop()
            return []

        path_p = find(root,[], p.val)
        path_q = find(root,[], q.val)

        l = 0
        while l < min(len(path_p), len(path_q)) and path_p[l].val == path_q[l].val:
            l += 1
        return path_p[l-1]

if __name__ == '__main__':
    root = bfs_load([3,5,1,6,2,0,8,None,None,7,4])
    s = Solution()
    s.lowestCommonAncestor(root, TreeNode(5), TreeNode(1))